package com.zy.tree;

import java.util.Arrays;

/**
 * @author zhaoyi
 * @date 2021/8/10 15:47
 * 二叉查找树要求，
 * 在树中的任意一个节点，
 * 其左子树中的每个节点的值，都要小于这个节点的值，
 * 而右子树节点的值都大于这个节点的值。
 * <p>
 * 第一种 基于数组的二叉树
 *
 * 基于数组的顺序存储法
 * > 完全二叉树基于数组的顺序存储法不会产生浪费空间.非完全二叉树会产生浪费空间
 * > 基于数组节省了指针
 *
 * 完全二叉树
 * 	1 叶子节点都在最底下两层
 * 	2 最后一层的叶子节点都靠左排,或者满
 * 	3 除最后一层，其他层的节点都满
 *
 */
public class BinaryTreeOnArray {

    //条数
    private Integer size;
    private Integer maxSize;
    private Integer[] list;


    public BinaryTreeOnArray(Integer maxSize) {
        this.size = 0;
        this.maxSize = maxSize;
        this.list = new Integer[maxSize];
    }

    //插入数据
    public void put(Integer data) {
        if (size == 0) {
            list[1] = data;
        } else {
            if (data > list[1]) {
                putIndex(3, data);
            } else {
                putIndex(2, data);
            }
        }
        size++;
    }



    /**
     * i 为数组的下标
     * 根节点存储在下标 i=1的位置,
     * 那左子节点存储在下标2*i=2的位置，
     * 右子节点存储在2*i+1=3的位置。以此类推
     */
    private void putIndex(int i, Integer data) {
        if (i > maxSize) {
            throw new IllegalArgumentException("超过容量限制");
        }
        Integer di = list[i];
        if (di == null) {
            list[i] = data;
        } else {
            if (data > di) {
                putIndex(i * 2 + 1, data);
            } else {
                putIndex(i * 2, data);
            }
        }
    }




    private void printTree(boolean flag) {
        if (!flag) {
            System.out.println(Arrays.toString(list));
        } else {
            System.out.println("树形打印");
            double value = Math.log(maxSize-1) / Math.log(2) + 1;
            int start = 1;
            for (int i = 0; i <= (int) value; i++) {
                int pow = (int) Math.pow(2, i);
                int end = start + pow;
                for (int j = start; j < end && j < maxSize  ; j++) {
                    System.out.print(list[j] + "  ");
                }
                start = end;
                System.out.println();
            }
        }

    }


    public static void main(String[] args) {
        BinaryTreeOnArray tree = new BinaryTreeOnArray(32);
        tree.put(4);
        tree.put(3);
        tree.put(5);
        tree.put(1);
        tree.put(2);
        tree.printTree(false);
        tree.printTree(true);
    }


}
